home *** CD-ROM | disk | FTP | other *** search
hhhhsssseeeeaaaarrrrcccchhhh((((3333CCCC)))) hhhhsssseeeeaaaarrrrcccchhhh((((3333CCCC)))) NNNNAAAAMMMMEEEE _hhhh_ssss_eeee_aaaa_rrrr_cccc_hhhh, _hhhh_cccc_rrrr_eeee_aaaa_tttt_eeee, _hhhh_dddd_eeee_ssss_tttt_rrrr_oooo_yyyy - manage hash search tables SSSSYYYYNNNNOOOOPPPPSSSSIIIISSSS _####_iiii_nnnn_cccc_llll_uuuu_dddd_eeee _<<<<_ssss_eeee_aaaa_rrrr_cccc_hhhh_...._hhhh_>>>> _EEEE_NNNN_TTTT_RRRR_YYYY _****_hhhh_ssss_eeee_aaaa_rrrr_cccc_hhhh _((((_EEEE_NNNN_TTTT_RRRR_YYYY _iiii_tttt_eeee_mmmm_,,,, _AAAA_CCCC_TTTT_IIII_OOOO_NNNN _aaaa_cccc_tttt_iiii_oooo_nnnn_))))_;;;; _iiii_nnnn_tttt _hhhh_cccc_rrrr_eeee_aaaa_tttt_eeee _((((_ssss_iiii_zzzz_eeee______tttt _nnnn_eeee_llll_))))_;;;; _vvvv_oooo_iiii_dddd _hhhh_dddd_eeee_ssss_tttt_rrrr_oooo_yyyy _((((_vvvv_oooo_iiii_dddd_))))_;;;; DDDDEEEESSSSCCCCRRRRIIIIPPPPTTTTIIIIOOOONNNN _hhhh_ssss_eeee_aaaa_rrrr_cccc_hhhh is a hash-table search routine generalized from Knuth (6.4) Algorithm D. It returns a pointer into a hash table indicating the location at which an entry can be found. The comparison function used by _hhhh_ssss_eeee_aaaa_rrrr_cccc_hhhh is _ssss_tttt_rrrr_cccc_mmmm_pppp [see _ssss_tttt_rrrr_iiii_nnnn_gggg(3C)]. _i_t_e_m is a structure of type _EEEE_NNNN_TTTT_RRRR_YYYY (defined in the _ssss_eeee_aaaa_rrrr_cccc_hhhh_...._hhhh header file) containing two pointers: _i_t_e_m._k_e_y points to the comparison key, and _i_t_e_m._d_a_t_a points to any other data to be associated with that key. (Pointers to types other than void should be cast to pointer-to-void.) _a_c_t_i_o_n is a member of an enumeration type _AAAA_CCCC_TTTT_IIII_OOOO_NNNN (defined in _ssss_eeee_aaaa_rrrr_cccc_hhhh_...._hhhh) indicating the disposition of the entry if it cannot be found in the table. _EEEE_NNNN_TTTT_EEEE_RRRR indicates that the item should be inserted in the table at an appropriate point. Given a duplicate of an existing item, the new item is not entered and _hhhh_ssss_eeee_aaaa_rrrr_cccc_hhhh returns a pointer to the existing item. _FFFF_IIII_NNNN_DDDD indicates that no entry should be made. Unsuccessful resolution is indicated by the return of a null pointer. _hhhh_cccc_rrrr_eeee_aaaa_tttt_eeee allocates sufficient space for the table, and must be called before _hhhh_ssss_eeee_aaaa_rrrr_cccc_hhhh is used. _n_e_l is an estimate of the maximum number of entries that the table will contain. This number may be adjusted upward by the algorithm in order to obtain certain mathematically favorable circumstances. _hhhh_dddd_eeee_ssss_tttt_rrrr_oooo_yyyy destroys the search table, and may be followed by another call to _hhhh_cccc_rrrr_eeee_aaaa_tttt_eeee. BBBBUUUUGGGGSSSS _H_s_e_a_r_c_h is compiled by Silicon Graphics with none of the flags named in NOTES defined. NNNNOOOOTTTTEEEESSSS _h_s_e_a_r_c_h uses _o_p_e_n _a_d_d_r_e_s_s_i_n_g with a _m_u_l_t_i_p_l_i_c_a_t_i_v_e hash function. However, its source code has many other options available which the user may select by compiling the _h_s_e_a_r_c_h source with the following symbols defined to the preprocessor: DDDDIIIIVVVV Use the _r_e_m_a_i_n_d_e_r _m_o_d_u_l_o _t_a_b_l_e _s_i_z_e as the hash function instead of the multiplicative algorithm. PPPPaaaaggggeeee 1111 hhhhsssseeeeaaaarrrrcccchhhh((((3333CCCC)))) hhhhsssseeeeaaaarrrrcccchhhh((((3333CCCC)))) UUUUSSSSCCCCRRRR Use a User Supplied Comparison Routine for ascertaining table membership. The routine should be named _h_c_o_m_p_a_r and should behave in a manner similar to _s_t_r_c_m_p [see _s_t_r_i_n_g(3C)]. CCCCHHHHAAAAIIIINNNNEEEEDDDD Use a linked list to resolve collisions. If this option is selected, the following other options become available. SSSSTTTTAAAARRRRTTTT Place new entries at the beginning of the linked list (default is at the end). SSSSOOOORRRRTTTTUUUUPPPP Keep the linked list sorted by key in ascending order. SSSSOOOORRRRTTTTDDDDOOOOWWWWNNNN Keep the linked list sorted by key in descending order. The source code should be consulted for further details. EEEEXXXXAAAAMMMMPPPPLLLLEEEE The following example will read in strings followed by two numbers and store them in a hash table, discarding duplicates. It will then read in strings and find the matching entry in the hash table and print it out. _####_iiii_nnnn_cccc_llll_uuuu_dddd_eeee _<<<<_ssss_tttt_dddd_iiii_oooo_...._hhhh_>>>> _####_iiii_nnnn_cccc_llll_uuuu_dddd_eeee _<<<<_ssss_eeee_aaaa_rrrr_cccc_hhhh_...._hhhh_>>>> _####_iiii_nnnn_cccc_llll_uuuu_dddd_eeee _<<<<_ssss_tttt_rrrr_iiii_nnnn_gggg_...._hhhh_>>>> _####_iiii_nnnn_cccc_llll_uuuu_dddd_eeee _<<<<_ssss_tttt_dddd_llll_iiii_bbbb_...._hhhh_>>>> _ssss_tttt_rrrr_uuuu_cccc_tttt _iiii_nnnn_ffff_oooo _{{{{ _////_**** _tttt_hhhh_iiii_ssss _iiii_ssss _tttt_hhhh_eeee _iiii_nnnn_ffff_oooo _ssss_tttt_oooo_rrrr_eeee_dddd _iiii_nnnn _tttt_aaaa_bbbb_llll_eeee _****_//// _iiii_nnnn_tttt _aaaa_gggg_eeee_,,,, _rrrr_oooo_oooo_mmmm_;;;; _////_**** _oooo_tttt_hhhh_eeee_rrrr _tttt_hhhh_aaaa_nnnn _tttt_hhhh_eeee _kkkk_eeee_yyyy _****_//// _}}}}_;;;; _####_dddd_eeee_ffff_iiii_nnnn_eeee _NNNN_UUUU_MMMM______EEEE_MMMM_PPPP_LLLL _5555_0000_0000_0000 _////_**** _#### _oooo_ffff _eeee_llll_eeee_mmmm_eeee_nnnn_tttt_ssss _iiii_nnnn _ssss_eeee_aaaa_rrrr_cccc_hhhh _tttt_aaaa_bbbb_llll_eeee _****_//// _mmmm_aaaa_iiii_nnnn_(((( _)))) _{{{{ _////_**** _ssss_pppp_aaaa_cccc_eeee _tttt_oooo _ssss_tttt_oooo_rrrr_eeee _ssss_tttt_rrrr_iiii_nnnn_gggg_ssss _****_//// PPPPaaaaggggeeee 2222 hhhhsssseeeeaaaarrrrcccchhhh((((3333CCCC)))) hhhhsssseeeeaaaarrrrcccchhhh((((3333CCCC)))) _cccc_hhhh_aaaa_rrrr _ssss_tttt_rrrr_iiii_nnnn_gggg______ssss_pppp_aaaa_cccc_eeee_[[[[_NNNN_UUUU_MMMM______EEEE_MMMM_PPPP_LLLL_****_2222_0000_]]]]_;;;; _////_**** _ssss_pppp_aaaa_cccc_eeee _tttt_oooo _ssss_tttt_oooo_rrrr_eeee _eeee_mmmm_pppp_llll_oooo_yyyy_eeee_eeee _iiii_nnnn_ffff_oooo _****_//// _ssss_tttt_rrrr_uuuu_cccc_tttt _iiii_nnnn_ffff_oooo _iiii_nnnn_ffff_oooo______ssss_pppp_aaaa_cccc_eeee_[[[[_NNNN_UUUU_MMMM______EEEE_MMMM_PPPP_LLLL_]]]]_;;;; _////_**** _nnnn_eeee_xxxx_tttt _aaaa_vvvv_aaaa_iiii_llll _ssss_pppp_aaaa_cccc_eeee _iiii_nnnn _ssss_tttt_rrrr_iiii_nnnn_gggg______ssss_pppp_aaaa_cccc_eeee _****_//// _cccc_hhhh_aaaa_rrrr _****_ssss_tttt_rrrr______pppp_tttt_rrrr _==== _ssss_tttt_rrrr_iiii_nnnn_gggg______ssss_pppp_aaaa_cccc_eeee_;;;; _////_**** _nnnn_eeee_xxxx_tttt _aaaa_vvvv_aaaa_iiii_llll _ssss_pppp_aaaa_cccc_eeee _iiii_nnnn _iiii_nnnn_ffff_oooo______ssss_pppp_aaaa_cccc_eeee _****_//// _ssss_tttt_rrrr_uuuu_cccc_tttt _iiii_nnnn_ffff_oooo _****_iiii_nnnn_ffff_oooo______pppp_tttt_rrrr _==== _iiii_nnnn_ffff_oooo______ssss_pppp_aaaa_cccc_eeee_;;;; _EEEE_NNNN_TTTT_RRRR_YYYY _iiii_tttt_eeee_mmmm_,,,, _****_ffff_oooo_uuuu_nnnn_dddd______iiii_tttt_eeee_mmmm_;;;; _////_**** _nnnn_aaaa_mmmm_eeee _tttt_oooo _llll_oooo_oooo_kkkk _ffff_oooo_rrrr _iiii_nnnn _tttt_aaaa_bbbb_llll_eeee _****_//// _cccc_hhhh_aaaa_rrrr _nnnn_aaaa_mmmm_eeee______tttt_oooo______ffff_iiii_nnnn_dddd_[[[[_3333_0000_]]]]_;;;; _iiii_nnnn_tttt _iiii _==== _0000_;;;; _////_**** _cccc_rrrr_eeee_aaaa_tttt_eeee _tttt_aaaa_bbbb_llll_eeee _****_//// _((((_vvvv_oooo_iiii_dddd_)))) _hhhh_cccc_rrrr_eeee_aaaa_tttt_eeee_((((_NNNN_UUUU_MMMM______EEEE_MMMM_PPPP_LLLL_))))_;;;; _wwww_hhhh_iiii_llll_eeee _((((_ssss_cccc_aaaa_nnnn_ffff_((((_""""_%%%%_ssss_%%%%_dddd_%%%%_dddd_""""_,,,, _ssss_tttt_rrrr______pppp_tttt_rrrr_,,,, _&&&&_iiii_nnnn_ffff_oooo______pppp_tttt_rrrr_----_>>>>_aaaa_gggg_eeee_,,,, _&&&&_iiii_nnnn_ffff_oooo______pppp_tttt_rrrr_----_>>>>_rrrr_oooo_oooo_mmmm_)))) _!!!!_==== _EEEE_OOOO_FFFF _&&&&_&&&& _iiii_++++_++++ _<<<< _NNNN_UUUU_MMMM______EEEE_MMMM_PPPP_LLLL_)))) _{{{{ _////_**** _pppp_uuuu_tttt _iiii_nnnn_ffff_oooo _iiii_nnnn _ssss_tttt_rrrr_uuuu_cccc_tttt_uuuu_rrrr_eeee_,,,, _aaaa_nnnn_dddd _ssss_tttt_rrrr_uuuu_cccc_tttt_uuuu_rrrr_eeee _iiii_nnnn _iiii_tttt_eeee_mmmm _****_//// _iiii_tttt_eeee_mmmm_...._kkkk_eeee_yyyy _==== _ssss_tttt_rrrr______pppp_tttt_rrrr_;;;; _iiii_tttt_eeee_mmmm_...._dddd_aaaa_tttt_aaaa _==== _((((_vvvv_oooo_iiii_dddd _****_))))_iiii_nnnn_ffff_oooo______pppp_tttt_rrrr_;;;; _ssss_tttt_rrrr______pppp_tttt_rrrr _++++_==== _ssss_tttt_rrrr_llll_eeee_nnnn_((((_ssss_tttt_rrrr______pppp_tttt_rrrr_)))) _++++ _1111_;;;; _iiii_nnnn_ffff_oooo______pppp_tttt_rrrr_++++_++++_;;;; _////_**** _pppp_uuuu_tttt _iiii_tttt_eeee_mmmm _iiii_nnnn_tttt_oooo _tttt_aaaa_bbbb_llll_eeee _****_//// _((((_vvvv_oooo_iiii_dddd_)))) _hhhh_ssss_eeee_aaaa_rrrr_cccc_hhhh_((((_iiii_tttt_eeee_mmmm_,,,, _EEEE_NNNN_TTTT_EEEE_RRRR_))))_;;;; _}}}} _////_**** _aaaa_cccc_cccc_eeee_ssss_ssss _tttt_aaaa_bbbb_llll_eeee _****_//// _iiii_tttt_eeee_mmmm_...._kkkk_eeee_yyyy _==== _nnnn_aaaa_mmmm_eeee______tttt_oooo______ffff_iiii_nnnn_dddd_;;;; _wwww_hhhh_iiii_llll_eeee _((((_ssss_cccc_aaaa_nnnn_ffff_((((_""""_%%%%_ssss_""""_,,,, _iiii_tttt_eeee_mmmm_...._kkkk_eeee_yyyy_)))) _!!!!_==== _EEEE_OOOO_FFFF_)))) _{{{{ _iiii_ffff _((((_((((_ffff_oooo_uuuu_nnnn_dddd______iiii_tttt_eeee_mmmm _==== _hhhh_ssss_eeee_aaaa_rrrr_cccc_hhhh_((((_iiii_tttt_eeee_mmmm_,,,, _FFFF_IIII_NNNN_DDDD_))))_)))) _!!!!_==== _NNNN_UUUU_LLLL_LLLL_)))) _{{{{ _////_**** _iiii_ffff _iiii_tttt_eeee_mmmm _iiii_ssss _iiii_nnnn _tttt_hhhh_eeee _tttt_aaaa_bbbb_llll_eeee _****_//// _((((_vvvv_oooo_iiii_dddd_))))_pppp_rrrr_iiii_nnnn_tttt_ffff_((((_""""_ffff_oooo_uuuu_nnnn_dddd _%%%%_ssss_,,,, _aaaa_gggg_eeee _==== _%%%%_dddd_,,,, _rrrr_oooo_oooo_mmmm _==== _%%%%_dddd_\\\\_nnnn_""""_,,,, _ffff_oooo_uuuu_nnnn_dddd______iiii_tttt_eeee_mmmm_----_>>>>_kkkk_eeee_yyyy_,,,, _((((_((((_ssss_tttt_rrrr_uuuu_cccc_tttt _iiii_nnnn_ffff_oooo _****_))))_ffff_oooo_uuuu_nnnn_dddd______iiii_tttt_eeee_mmmm_----_>>>>_dddd_aaaa_tttt_aaaa_))))_----_>>>>_aaaa_gggg_eeee_,,,, _((((_((((_ssss_tttt_rrrr_uuuu_cccc_tttt _iiii_nnnn_ffff_oooo _****_))))_ffff_oooo_uuuu_nnnn_dddd______iiii_tttt_eeee_mmmm_----_>>>>_dddd_aaaa_tttt_aaaa_))))_----_>>>>_rrrr_oooo_oooo_mmmm_))))_;;;; _}}}} _eeee_llll_ssss_eeee _{{{{ _((((_vvvv_oooo_iiii_dddd_))))_pppp_rrrr_iiii_nnnn_tttt_ffff_((((_""""_nnnn_oooo _ssss_uuuu_cccc_hhhh _eeee_mmmm_pppp_llll_oooo_yyyy_eeee_eeee _%%%%_ssss_\\\\_nnnn_""""_,,,, _nnnn_aaaa_mmmm_eeee______tttt_oooo______ffff_iiii_nnnn_dddd_))))_;;;; _}}}} _}}}} _rrrr_eeee_tttt_uuuu_rrrr_nnnn _0000_;;;; _}}}} PPPPaaaaggggeeee 3333 hhhhsssseeeeaaaarrrrcccchhhh((((3333CCCC)))) hhhhsssseeeeaaaarrrrcccchhhh((((3333CCCC)))) SSSSEEEEEEEE AAAALLLLSSSSOOOO _bbbb_ssss_eeee_aaaa_rrrr_cccc_hhhh(3C), _llll_ssss_eeee_aaaa_rrrr_cccc_hhhh(3C), _mmmm_aaaa_llll_llll_oooo_cccc(3C), _mmmm_aaaa_llll_llll_oooo_cccc(3X), _ssss_tttt_rrrr_iiii_nnnn_gggg(3C), _tttt_ssss_eeee_aaaa_rrrr_cccc_hhhh(3C). DDDDIIIIAAAAGGGGNNNNOOOOSSSSTTTTIIIICCCCSSSS _hhhh_ssss_eeee_aaaa_rrrr_cccc_hhhh returns a null pointer if either the action is _FFFF_IIII_NNNN_DDDD and the item could not be found or the action is _EEEE_NNNN_TTTT_EEEE_RRRR and the table is full. _hhhh_cccc_rrrr_eeee_aaaa_tttt_eeee returns zero if it cannot allocate sufficient space for the table. NNNNOOOOTTTTEEEESSSS _hhhh_ssss_eeee_aaaa_rrrr_cccc_hhhh and _hhhh_cccc_rrrr_eeee_aaaa_tttt_eeee use _mmmm_aaaa_llll_llll_oooo_cccc(3C) to allocate space. Only one hash search table may be active at any given time. PPPPaaaaggggeeee 4444 
